/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/3sum-closest
   @Language: C++
   @Datetime: 16-02-15 06:10
   */

class Solution {
public:    
	/**
	 * @param numbers: Give an array numbers of n integer
	 * @param target: An integer
	 * @return: return the sum of the three integers
	 *          the sum closest target.
	 */
	/** Tips : This is similar to problem 57 3sum , visit it for full notes
	 *  only find the closest sum to target, so do not attend the duplication
	 * */
	int threeSumClosest(vector<int> nums, int tar) {
		// write your code here
		sort(nums.begin(),nums.end());
		int ans = INT_MAX;
		for(int i=0; i<nums.size(); ++i){
			for(int j=i+1, k=nums.size()-1; j<k;){
				int sum = nums[i]+nums[j]+nums[k];
				// update the closest answer
				ans = (abs(tar-sum)<abs(tar-ans) ? sum:ans);
				if (sum > tar) --k;
				else if (sum < tar) ++j;
				else return sum;	// sum equal to target
			}
		}
		return ans;
	}
};
